class Solution
{
public:
    int largestIsland(vector<vector<int>> &grid)
    {
        this->n = grid.size();
        for (int i = 0; i < this->n; ++i)
        {
            for (int j = 0; j < this->n; ++j)
            {
                if (grid[i][j] == 1)
                {
                    bfsAddContinuousArea(grid, {i, j});
                }
            }
        }
        int maxArea = 0;
        for (int i = 0; i < this->n; ++i)
        {
            for (int j = 0; j < this->n; ++j)
            {
                if (grid[i][j] == 0)
                {
                    unordered_set<int> adjacentIds;
                    int area = 0;
                    if (i - 1 >= 0 && grid[i - 1][j] != 0)
                    {
                        adjacentIds.insert(grid[i - 1][j]);
                    }
                    if (i + 1 < n && grid[i + 1][j] != 0)
                    {
                        adjacentIds.insert(grid[i + 1][j]);
                    }
                    if (j - 1 >= 0 && grid[i][j - 1] != 0)
                    {
                        adjacentIds.insert(grid[i][j - 1]);
                    }
                    if (j + 1 < n && grid[i][j + 1] != 0)
                    {
                        adjacentIds.insert(grid[i][j + 1]);
                    }
                    for (auto id : adjacentIds)
                    {
                        area += this->idAreas[id];
                    }
                    area += 1;
                    maxArea = max(area, maxArea);
                }
            }
        }
        if (maxArea == 0) // 当且仅当grid为全1
        {
            return this->n * this->n;
        }
        return maxArea;
    }

private:
    using Point = pair<int, int>;
    unordered_map<int, int> idAreas;
    int id = 2;
    int n;

    void bfsAddContinuousArea(vector<vector<int>> &grid, Point start)
    {
        queue<Point> q;
        q.push(start);
        grid[start.first][start.second] = this->id;
        int area = 0;
        while (!q.empty())
        {
            auto point = q.front();
            q.pop();
            ++area;
            if (point.first - 1 >= 0 && grid[point.first - 1][point.second] == 1)
            {
                q.push({point.first - 1, point.second});
                grid[point.first - 1][point.second] = this->id;
            }
            if (point.first + 1 < this->n && grid[point.first + 1][point.second] == 1)
            {
                q.push({point.first + 1, point.second});
                grid[point.first + 1][point.second] = this->id;
            }
            if (point.second - 1 >= 0 && grid[point.first][point.second - 1] == 1)
            {
                q.push({point.first, point.second - 1});
                grid[point.first][point.second - 1] = this->id;
            }
            if (point.second + 1 < this->n && grid[point.first][point.second + 1] == 1)
            {
                q.push({point.first, point.second + 1});
                grid[point.first][point.second + 1] = this->id;
            }
        }
        this->idAreas[this->id] = area;
        ++this->id;
    }
};